//////////////////////////////////////
// Fast Container Library           //
// MIT License - Copyright (c) 2012 //
//////////////////////////////////////

#pragma once

#include "common.h"
#include "type_traits.h"
#include "iterator_traits.h"
#include "functional.h"
#include "algobase.h"


// copy.h (modifying sequence operations)
//
// swap				(algobase.h)
// swap_ranges		(algobase.h)
// iter_swap		(algobase.h)
// fill				(algobase.h)
// fill				(algobase.h)
// fill_n           (algobase.h)
// copy				(algobase.h)
// copy_n           (algobase.h)
// copy_backward    (algobase.h)
// copy_if
// remove_copy
// remove_copy_if
// remove
// remove_if
// unique
// unique_copy
// replace
// replace_if
// replace_copy_if
// reverse
// reverse_copy	    (algobase.h)
// generate
// generate_n
// rotate
// rotate_copy
// transform

FC_NAMESPACE_BEGIN


// copy_if

template <class InputIterator, class OutputIterator, class UnaryPredicate> inline
	OutputIterator copy_if( InputIterator first, InputIterator last, OutputIterator result, UnaryPredicate predicate )
	{
		for( ; first != last; ++first )
			if( predicate(*first) )
				*result = *first, ++result;
		return result;
	}


// remove_copy

template <class InputIterator, class OutputIterator, class T> inline
	OutputIterator remove_copy( InputIterator first, InputIterator last, OutputIterator result, const T& value )
	{
		for( ; first != last; ++first )
			if( !(*first == value) )
				*result = *first, ++result;
		return result;
	}


// remove_copy_if

template <class InputIterator, class OutputIterator, class UnaryPredicate> inline
	OutputIterator remove_copy_if( InputIterator first, InputIterator last, OutputIterator result, UnaryPredicate predicate )
	{
		for( ; first != last; ++first )
			if( !predicate(*first) )
				*result = *first, ++result;
		return result;
	}


// remove

template <class ForwardIterator, class T> inline
	ForwardIterator remove( ForwardIterator first, ForwardIterator last, const T& value )
	{
		first = find( first, last, value );
		if( first != last )
		{
			ForwardIterator it(first);
			return remove_copy( ++it, last, first, value );
		}

		return first;
	}


// remove_if

template <class ForwardIterator, class UnaryPredicate> inline
	ForwardIterator remove_if( ForwardIterator first, ForwardIterator last, UnaryPredicate predicate )
	{
		first = find_if<ForwardIterator, UnaryPredicate>( first, last, predicate );
		if( first != last )
		{
			ForwardIterator it(first);
			return remove_copy_if<ForwardIterator, ForwardIterator, UnaryPredicate>( ++it, last, first, predicate );
		}

		return first;
	}


// unique

template <class ForwardIterator, class BinaryPredicate> inline
	ForwardIterator unique( ForwardIterator first, ForwardIterator last, BinaryPredicate predicate )
	{
		ForwardIterator result = first;

		if( FC_LIKELY(first != last) )
		{
			while( ++first != last )
				if( !predicate(*result, *first) )
					*++result = *first;
		}

		return ++result;
	}

template <class ForwardIterator> inline
	ForwardIterator unique( ForwardIterator first, ForwardIterator last )
	{
		ForwardIterator result = first;

		if( FC_LIKELY(first != last) )
		{
			while( ++first != last )
				if( !(*result == *first) )
					*++result = *first;
		}

		return ++result;
	}


// unique_copy

template <class InputIterator, class OutputIterator, class BinaryPredicate> inline
	OutputIterator unique_copy( InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate predicate )
	{
		if( FC_LIKELY(first != last) )
		{
			*result = *first;
			while( ++first != last )
				if( !predicate(*result, *first) )
					*(++result) = *first;

			return ++result;
		}
		return result;
	}

template <class InputIterator, class OutputIterator> inline
	OutputIterator unique_copy( InputIterator first, InputIterator last, OutputIterator result )
	{
		if( FC_LIKELY(first != last) )
		{
			*result = *first;
			while( ++first != last )
				if( !(*result == *first) )
					*(++result) = *first;

			return ++result;
		}
		return result;
	}


// replace

template <class ForwardIterator, class T> inline
	void replace( ForwardIterator first, ForwardIterator last, const T& oldValue, const T& newValue )
	{
		for( ; first != last; ++first )
			if( *first == oldValue )
				*first = newValue;
	}


// replace_if

template <class ForwardIterator, class UnaryPredicate, class T> inline
	void replace_if( ForwardIterator first, ForwardIterator last, UnaryPredicate predicate, const T& newValue )
	{
		for( ; first != last; ++first )
			if( predicate(*first) )
				*first = newValue;
	}


// replace_copy

template <class InputIterator, class OutputIterator, class T> inline
	OutputIterator replace_copy( InputIterator first, InputIterator last, OutputIterator result,
	const T& oldValue, const T& newValue )
	{
		for( ; first != last; ++first, ++result )
			*result = (*first == oldValue) ? newValue : *first;
		return result;
	}


// replace_copy_if

template <class InputIterator, class OutputIterator, class T, class UnaryPredicate> inline
	OutputIterator replace_copy_if( InputIterator first, InputIterator last, OutputIterator result,
	UnaryPredicate predicate, const T& newValue )
	{
		for( ; first != last; ++first, ++result )
			*result = predicate(*first) ? newValue : *first;
		return result;
	}


// reverse

namespace internal
{
	template <class RandomAccessIterator> inline
	void reverse( RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag )
	{
		for( ; first < --last; ++first )
			iter_swap(first, last);
	}

	template <class BidirectionalIterator> inline
	void reverse( BidirectionalIterator first, BidirectionalIterator last, bidirectional_iterator_tag )
	{
		for( ; (first != last) && (first != --last); ++first )
			iter_swap(first, last);
	}
}

template <class BidirectionalIterator> inline
	void reverse( BidirectionalIterator first, BidirectionalIterator last )
	{
		internal::reverse( first, last,
			typename iterator_traits<BidirectionalIterator>::iterator_type() );
	}


// generate

template <class ForwardIterator, class Generator> inline
	void generate( ForwardIterator first, ForwardIterator last, Generator gen )
	{
		for( ; first != last; ++first )
			*first = gen();
	}


// generate_n

template <class ForwardIterator, class Generator> inline
	ForwardIterator generate_n( ForwardIterator first, size_t n, Generator gen )
	{
		for( size_t i(0); i < n; ++first, --n )
			*first = gen();
		return first;
	}


namespace internal
{
	// rotate
	// todo: this can be optimized...

	template <class ForwardIterator> inline
	void rotate( ForwardIterator first, ForwardIterator middle, ForwardIterator last, forward_iterator_tag )
	{
		for( ForwardIterator next = middle; first != next; )
		{
			swap(*first++, *next++);
			if( next == last )
				next = middle;
			else if( first == middle )
				middle = next;
		}

		/*
		for( ForwardIterator next = middle; first != next; )
		{
			fc::swap(first, next);
			++first;
			++next;
			if( next == last )
				next = middle;
			else if( first == middle )
				middle = next;
		}
		*/
	}
}


// rotate

template <class ForwardIterator> inline
	void rotate( ForwardIterator first, ForwardIterator middle, ForwardIterator last )
	{
		internal::rotate( first, middle, last,
			typename iterator_traits<ForwardIterator>::iterator_type() );
	}


// rotate_copy

template <class ForwardIterator, class OutputIterator> inline
	OutputIterator rotate_copy( ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result )
	{
		return copy( first, middle, copy(middle, last, result) );
	}


// transform (unary)

template <class InputIterator, class OutputIterator, class UnaryOperation> inline
	OutputIterator transform( InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op )
	{
		for( ; first != last; ++first, ++result )
			*result = op(*first);
		return result;
	}


// transform (binary)

template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation> inline
	OutputIterator transform( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
	OutputIterator result, BinaryOperation op )
	{
		for( ; first1 != last1; ++first1, ++first2, ++result )
			*result = op(*first1, *first2);
		return result;
	}




FC_NAMESPACE_END
